import collections
from typing import List


class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        ##  滑动窗口 + 哈希表
        cnt, l = len(words), len(words[0])

        i, j = 0, cnt*l-1 #i和j分别指向0和words的长度
        res = []

        origin_words = collections.Counter(words)  #统计单词的频率

        while j < len(s):
            windows = s[i:j+1]

            tmp = []
            for k in range(0, len(windows), l):
                tmp.append(windows[k:k+l])
            if collections.Counter(tmp) == origin_words:
                res.append(i)
            i+=1
            j+=1
        return res
